package com.cuz.daileetcode.treedp;

import java.util.List;
import java.util.Stack;

/**
 * @author cuzz
 * @version 1.0
 * @description: 见 【树形dp：派对的最大快乐值】
 * @date 14:37 2022/1/2
 **/
public class PartyMaxHappiness {

    static class Employee {
        int happy;
        List<Employee> subordinate;
    }

    static class SubTreeInfo {
        int invitedHappiness;
        int noInvitedHappiness;

        public SubTreeInfo(int invitedHappiness, int noInvitedHappiness) {
            this.invitedHappiness = invitedHappiness;
            this.noInvitedHappiness = noInvitedHappiness;
        }
    }


    public static int getMaxHappiness(Employee boss) {
        if (boss==null){
            return 0;
        }
        SubTreeInfo subTreeInfo = recursionGetSubTreeInfo(boss);
        return Math.max(subTreeInfo.invitedHappiness,subTreeInfo.noInvitedHappiness);
    }

    public static SubTreeInfo recursionGetSubTreeInfo(Employee nowEmployee) {
        //对于最底层员工 邀请 那么快乐值是自己的快乐值 反之是0 因为底层员工没有下级so不需要继续递归了
        if (nowEmployee.subordinate == null || nowEmployee.subordinate.size() == 0) {
            return new SubTreeInfo(nowEmployee.happy, 0);
        }
        int invitedHappiness = nowEmployee.happy;
        int noInvitedHappiness = 0;
        List<Employee> subordinate = nowEmployee.subordinate;
        for (Employee temp : subordinate) {
            //当前下级（temp）邀请or 不邀请的快乐值
            SubTreeInfo nowSubInfo = recursionGetSubTreeInfo(temp);
            //如果邀请了 nowEmployee 那么 temp不可以来 so 加上的是temp不来的快乐值
            invitedHappiness += nowSubInfo.noInvitedHappiness;
            //如果邀请nowEmployee 那么取temp来or不来快乐值的max
            noInvitedHappiness += Math.max(nowSubInfo.invitedHappiness, nowSubInfo.noInvitedHappiness);
        }
        //返回邀请和不邀请对应的快乐值
        return new SubTreeInfo(invitedHappiness, noInvitedHappiness);
    }
}
